﻿/*
题目：验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

https://leetcode.cn/problems/validate-binary-search-tree/
*/

#include <iostream>
#include <random>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class Solution {
public:
    // 左子树的每个结点都要大于右子树的每个结点
    // 向下遍历的时候，持续更新最大值和最小值
    bool isValidBST(TreeNode* root) {
        return fn(root, LONG_MIN, LONG_MAX);
    }

    bool fn(TreeNode* root, long long min, long long max) {
        if (root == nullptr)    return true;

        if (root->val <= min || root->val >= max)   return false;

        // 向左子树遍历的时候，当前结点就是 左子树的最大值
        // 同理，遍历右子树的时候，当前结点就是 右子树的最小值
        return fn(root->left, min, root->val) && fn(root->right, root->val, max);
    }
};
